package nowcoder.others;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 最大上升子序列和
 *
 * @author briarbear
 * @blog http://briarbear.github.io
 * @create 2018-08-28-22:57
 */
public class MaxRiseSubSum {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int len  = scanner.nextInt(); //数组长度
            int[] array = new int[len];  //数组
            int[] dp = new int[len];   //dp数组 dp[i] 表示到i为止最大的升序和
            for (int i = 0; i < len; i++) {
                array[i] = scanner.nextInt();
                dp[i] = array[i]; //dp[i]默认为当前元素值
            }

            for (int i = 0; i < len; i++) {
                for (int j = 0; j < i; j++) {
                    if (array[j] < array[i])
                        dp[i] = Math.max(dp[j] + array[i],dp[i]);
                }
            }

            System.out.println(Arrays.stream(dp).max().getAsInt());
        }
    }
}
